package day_2023_7_to_10;

/**
 * @author haomin
 * @date 2023/08/03 00:07
 **/
public class Day_8_3 {
    class Solution {
        public TreeNode mirrorTree(TreeNode root) {
            if (root == null) return root;
            TreeNode l = root.left;
            TreeNode r = root.right;
            root.left = r;
            root.right = l;
            mirrorTree(root.left);
            mirrorTree(root.right);
            return root;
        }
    }
    class Solution2 {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;
            return isSymmetricHelper(root.left, root.right);
        }

        public boolean isSymmetricHelper(TreeNode l , TreeNode r) {
            if (l == null && r == null) return true;
            if (l == null || r == null) return false;
            return l.val == r.val && isSymmetricHelper(l.left, r.right) && isSymmetricHelper(l.right, r.left);
        }
    }
    class Solution3 {
        public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length == 0) return false;
            int m = board.length, n = board[0].length;
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(word.charAt(0) == board[i][j]) {
                        if(existHelper(board, word, i, j, m, n, 0)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        public boolean existHelper(char[][] board, String word, int i, int j, int m, int n, int k) {
            if(k >= word.length()) return true;
            if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k)) return false;
            board[i][j] += 64;
            boolean res = existHelper(board, word, i+1, j, m, n, k+1) ||
                    existHelper(board, word, i-1, j, m, n, k+1) ||
                    existHelper(board, word, i, j+1, m, n, k+1) ||
                    existHelper(board, word, i, j-1, m, n, k+1);
            board[i][j] -= 64;
            return res;
        }
    }
}